
#include <iostream>
#include <stdlib.h>
#include <time.h>

unsigned randomNumber(unsigned range){
	return (rand() | rand() * (RAND_MAX + 1)) % range;
}

template <typename T>
void quickSort(T* arrayToSort, unsigned endIndex, unsigned startIndex = 0){
	if(endIndex <= startIndex) return;
	
	unsigned baseIndex = randomNumber(endIndex - startIndex) + startIndex;
	
	T temp = arrayToSort[baseIndex];
	arrayToSort[baseIndex] = arrayToSort[startIndex];
	arrayToSort[startIndex] = temp;
	
	unsigned firstNotLess = startIndex + 1;
	while(firstNotLess < endIndex && arrayToSort[firstNotLess] < temp){
		firstNotLess++;
	}
	
	for(unsigned i = firstNotLess + 1; i < endIndex; i++){
		if(arrayToSort[i] < arrayToSort[startIndex]){
			temp = arrayToSort[i];
			arrayToSort[i] = arrayToSort[firstNotLess];
			arrayToSort[firstNotLess] = temp;
			firstNotLess++;
		}
	}
	temp = arrayToSort[startIndex];
	arrayToSort[startIndex] = arrayToSort[firstNotLess-1];
	arrayToSort[firstNotLess-1] = temp;
	
	quickSort(arrayToSort, firstNotLess - 1, startIndex);
	quickSort(arrayToSort, endIndex, firstNotLess);
}

template <typename T> class ArrayHeap{
protected:
	inline static unsigned getParent(unsigned x){
		return (x - 1 >> 1);
	}
	inline static unsigned getLeft(unsigned x){
		return ((x << 1) + 1);	// 2*x+1
	}
	inline static unsigned getRight(unsigned x){
		return (x + 1 << 1);	// 2*x+2 = 2*(x+1)
	}
public:
	static void heapSort(T* arrayToSort, unsigned length){
		unsigned i, tempIndex, leftIndex, rightIndex;
		T temp;
	#if 1	// make it a heap, bottom up
		i = (length >> 1);
		do{
			tempIndex = i;
			while(true){
				leftIndex = getLeft(tempIndex);
				if(leftIndex >= length) break;
				rightIndex = leftIndex + 1;
				if(rightIndex < length &&
						arrayToSort[leftIndex] < arrayToSort[rightIndex]){
					if(arrayToSort[rightIndex] > arrayToSort[tempIndex]){
						temp = arrayToSort[tempIndex];
						arrayToSort[tempIndex] = arrayToSort[rightIndex];
						arrayToSort[rightIndex] = temp;
						tempIndex = rightIndex;
					}else break;
				}else if(arrayToSort[leftIndex] > arrayToSort[tempIndex]){
					temp = arrayToSort[tempIndex];
					arrayToSort[tempIndex] = arrayToSort[leftIndex];
					arrayToSort[leftIndex] = temp;
					tempIndex = leftIndex;
				}else break;
			}
		}while(i-- > 0);
	#else	// make it a heap, top down
		for(i = 1; i < length; i++){
			unsigned tempIndex = i, parentIndex = getParent(i);
			do{
				if(arrayToSort[tempIndex] > arrayToSort[parentIndex]){
					T temp = arrayToSort[tempIndex];
					arrayToSort[tempIndex] = arrayToSort[parentIndex];
					arrayToSort[parentIndex] = temp;
				}else break;
				tempIndex = parentIndex;
				parentIndex = getParent(parentIndex);
			}while(tempIndex > 0);
		}
	#endif
	
		while(length-- > 1){
			temp = arrayToSort[0];
			arrayToSort[0] = arrayToSort[length];
			arrayToSort[length] = temp;
			tempIndex = 0;
			while(true){
				leftIndex = getLeft(tempIndex);
				if(leftIndex >= length) break;
				rightIndex = leftIndex + 1;
				if(rightIndex < length &&
						arrayToSort[leftIndex] < arrayToSort[rightIndex]){
					if(arrayToSort[rightIndex] > arrayToSort[tempIndex]){
						temp = arrayToSort[tempIndex];
						arrayToSort[tempIndex] = arrayToSort[rightIndex];
						arrayToSort[rightIndex] = temp;
						tempIndex = rightIndex;
					}else break;
				}else if(arrayToSort[leftIndex] > arrayToSort[tempIndex]){
					temp = arrayToSort[tempIndex];
					arrayToSort[tempIndex] = arrayToSort[leftIndex];
					arrayToSort[leftIndex] = temp;
					tempIndex = leftIndex;
				}else break;
			}
		}
	}
};

const unsigned NN = 64;
int increasing[2][NN], decreasing[2][NN], random[2][NN];
int main(){
	srand(time(NULL));
	unsigned i;
	for(i=0; i<NN; i++){
		increasing[0][i] = increasing[1][i] = i;
		decreasing[0][i] = decreasing[1][i] = NN - i;
		random[0][i] = random[1][i] = (rand() & 0x3F);
	}
	quickSort(increasing[0], NN);
	quickSort(decreasing[0], NN);
	quickSort(random[0], NN);
	for(i=0; i<NN; i++) std::cout << increasing[0][i] << '\t';
	std::cout << std::endl;
	for(i=0; i<NN; i++) std::cout << decreasing[0][i] << '\t';
	std::cout << std::endl;
	for(i=0; i<NN; i++) std::cout << random[0][i] << '\t';
	std::cout << std::endl << std::endl;
	
	ArrayHeap<int>::heapSort(increasing[1], NN);
	ArrayHeap<int>::heapSort(decreasing[1], NN);
	ArrayHeap<int>::heapSort(random[1], NN);
	for(i=0; i<NN; i++) std::cout << increasing[1][i] << '\t';
	std::cout << std::endl;
	for(i=0; i<NN; i++) std::cout << decreasing[1][i] << '\t';
	std::cout << std::endl;
	for(i=0; i<NN; i++) std::cout << random[1][i] << '\t';
	std::cout << std::endl;
	
	return 0;
}
